# Leetcode420算法复杂度分析
# 时间复杂度：O(N^2)，N为字符串长度。最坏情况下每次都要遍历整个字符串k次。
# 空间复杂度：O(N)，主要用于存储中间结果。

import matplotlib.pyplot as plt
from alg import Solution
import numpy as np
import time
import random
import string

# 基础算法正确性检验
def check_correctness():
    so = Solution()
    test_cases = [
        (("1432219", 3), "1219"),
        (("10200", 1), "200"),
        (("10", 2), "0"),
        (("1234567890", 9), "0"),
        (("112", 1), "11"),
        (("10001", 4), "0"),
        (("9", 1), "0"),
        (("112", 2), "1"),
    ]
    for i, ((num, k), expected) in enumerate(test_cases):
        result = so.removeKdigits(num, k)
        print(f"用例{i+1}: 输入 num='{num}', k={k}，期望输出={expected}，实际输出={result}", end=' ')
        if result == expected:
            print("✅ 通过")
        else:
            print(f"❌ 未通过: 期望={expected}，实际={result}")
            assert False

class test_Leetcode420:
    so = Solution()
    lengths = [128, 256, 512, 1024, 2048, 4096]
    times = []
    for length in lengths:
        num = ''.join(random.choices('123456789', k=1)) + ''.join(random.choices('0123456789', k=length-1))
        k = length // 2
        start_time = time.perf_counter()
        so.removeKdigits(num, k)
        end_time = time.perf_counter()
        elapsed_time = end_time - start_time
        times.append(elapsed_time)
        print(f"长度为{length}的测试用例，运行时间为{elapsed_time:.6f}秒")

    n = np.array(lengths, dtype=np.float64)
    n2 = n ** 2
    n_log = n * np.log2(n + 1)

    def normalization(ref, base):
        return [x / ref[0] * base[0] for x in ref]

    plt.figure(figsize=(10, 6))
    plt.plot(n, times, 'bo-', label="Measured Time", linewidth=2)
    plt.plot(n, normalization(n2, times), 'r--', label="O(n^2)", linewidth=2)
    plt.plot(n, normalization(n_log, times), 'g--', label="O(nlogn) Scaled", linewidth=2)
    plt.plot(n, normalization(n, times), 'm--', label="O(n) Scaled", linewidth=2)
    plt.yscale('log')
    plt.xlabel('Length of input string')
    plt.ylabel('Run Times (seconds, log scale)')
    plt.title('Leetcode420 Performance Analysis')
    plt.grid(True)
    plt.legend()
    plt.tight_layout()
    plt.show()
    plt.savefig('Leetcode420.png')

if __name__ == "__main__":
    print("基础算法正确性检验：")
    check_correctness()
    print("\n开始性能分析：")
    test = test_Leetcode420()
